/*
 *  linux/fs/bitmap.c
 *
 *  (C) 1991  Linus Torvalds
 */
// bitmap.c 程序含有处理 i 节点和磁盘块位图的代码
/* bitmap.c contains the code that handles the inode and block bitmaps */
#include <string.h>         // 字符串头文件 主要定义了一些有关字符串操作的嵌入函数
                            // 主要使用了其中的 memset（）函数
#include <linux/sched.h>    // 调度程序头文件 定义任务结构task_struct 初始任务0的数据
#include <linux/kernel.h>   // 内核头文件 含有一些内核常用函数的原形定义
// 将指定地址（addr）处的一块内存清零 嵌入汇编程序宏  输入 eax=0 ecx=数据块大小 BLOCK_SIZE/4 edi=addr
#define clear_block(addr) \
__asm__("cld\n\t" \         // 清方向位
	"rep\n\t" \             // 重复执行存储数据（0）
	"stosl" \
	::"a" (0),"c" (BLOCK_SIZE/4),"D" ((long) (addr)):"cx","di")
// 置位指定地址开始的第nr个位偏移处的比特位（nr可以大于32！） 返回原比特位（0或1）输入：%0 -eax（返回值） %1-eax（0） %2-nr 位偏移值 %3-（addr）addr的内容
#define set_bit(nr,addr) ({\
register int res __asm__("ax"); \
__asm__ __volatile__("btsl %2,%3\n\tsetb %%al": \
"=a" (res):"0" (0),"r" (nr),"m" (*(addr))); \
res;})
// 复位指定地址开始的第nr位偏移处的比特位 返回原比特位的反码（1或0） 输入：%0 -eax（返回值） %1-eax（0） %2-nr 位偏移值 %3-（addr）addr的内容
#define clear_bit(nr,addr) ({\
register int res __asm__("ax"); \
__asm__ __volatile__("btrl %2,%3\n\tsetnb %%al": \
"=a" (res):"0" (0),"r" (nr),"m" (*(addr))); \
res;})
// 从 addr 开始寻找第1个0值比特位 输入：%0-ecx（返回值） %1-ecx（0） %2-esi（addr） 在addr指定地址开始的位图中寻找第1个是0的比特位 并将其距离addr的比特位偏移值返回
#define find_first_zero(addr) ({ \
int __res; \
__asm__("cld\n" \               // 清方向位
	"1:\tlodsl\n\t" \           // 取【esi】->eax
	"notl %%eax\n\t" \          // eax 中每位取反
	"bsfl %%eax,%%edx\n\t" \    // 从位0扫描eax中是1的第1个位 其偏移值->edx
	"je 2f\n\t" \               // 如果eax中全是0 则向前跳转到标号2处（40行）
	"addl %%edx,%%ecx\n\t" \    // 偏移值加入ecx（其中是位图中首个是0的比特位的偏移值）
	"jmp 3f\n" \                // 向前跳转到标号3处（结束）
	"2:\taddl $32,%%ecx\n\t" \  // 没有找到 0 比特位 则将ecx加上1个长字的位偏移量32
	"cmpl $8192,%%ecx\n\t" \    // 已经扫描了8192位（1024字节）了吗
	"jl 1b\n" \                 // 若还没有扫描完1块数据 则向前跳转到标号1处，继续
	"3:" \                      // 结束 此时ecx中是位偏移量
	:"=c" (__res):"c" (0),"S" (addr):"ax","dx","si"); \
__res;})
// 释放设备dev上数据区中的逻辑块 block 复位指定逻辑块 block 的逻辑块位图比特位 参数 dev-是设备号 block是逻辑块号（盘块号）
void free_block(int dev, int block)
{
	struct super_block * sb;
	struct buffer_head * bh;
    // 取指定设备dev的超级块，如果指定设备不存在 则出错死机
	if (!(sb = get_super(dev)))
		panic("trying to free block on nonexistent device");
	if (block < sb->s_firstdatazone || block >= sb->s_nzones)   // 若逻辑块号小于第一个逻辑块号或者大于设备上总逻辑块数 则出错 死机
		panic("trying to free block not in datazone");
	bh = get_hash_table(dev,block); // 从hash表中寻找该块数据 若找到了则判断其有效性，并清已修改和更新标志 释放该数据块 该段代码的主要用途是： 如果该逻辑块当前存在于高速缓冲中，就释放对应的缓冲块
	if (bh) {
		if (bh->b_count != 1) {
			printk("trying to free block (%04x:%d), count=%d\n",
				dev,block,bh->b_count);
			return;
		}
		bh->b_dirt=0;       // 复位脏（已修改）标志位
		bh->b_uptodate=0;   // 复位更新标志
		brelse(bh);
	}   // 计算block在数据区开始算起的数据逻辑块号（从1开始计数） 然后对逻辑块（区块）位图进行操作 复位对应的比特位 若对应比特位原来即是0 则出错 死机
	block -= sb->s_firstdatazone - 1 ;  // block = block-(-1)
	if (clear_bit(block&8191,sb->s_zmap[block/8192]->b_data)) {
		printk("block (%04x:%d) ",dev,block+sb->s_firstdatazone-1);
		panic("free_block: bit already cleared");
	}
	sb->s_zmap[block/8192]->b_dirt = 1; // 置相应逻辑块位图所在缓冲区已修改标志
}
// 向设备dev申请一个逻辑块（盘块 区块） 返回逻辑块号（盘块号） 置位指定逻辑块block的逻辑块位图比特位
int new_block(int dev)
{
	struct buffer_head * bh;
	struct super_block * sb;
	int i,j;
    // 从设备dev取超级块 如果指定设备不存在 则出错死机
	if (!(sb = get_super(dev)))
		panic("trying to get new block from nonexistant device");
	j = 8192;   // 扫描逻辑块位图 寻找第一个0比特位 寻找空闲逻辑块 获取放置该逻辑块的块号
	for (i=0 ; i<8 ; i++)
		if (bh=sb->s_zmap[i])
			if ((j=find_first_zero(bh->b_data))<8192)
				break;
	if (i>=8 || !bh || j>=8192) // 如果全部扫描完还没找到（i>=8或j>=8192）或者位图所在的缓冲块无效（bh=NULL）则返回0 退出（没有空闲逻辑块）
		return 0;
	if (set_bit(j,bh->b_data))
		panic("new_block: bit already set");
	bh->b_dirt = 1; // 置对应缓冲区块的已修改标志 如果新逻辑块大于该设备块大于该设备上的总逻辑块数 则说明指定逻辑块在对应设备上不存在 申请失败 返回0 退出
	j += i*8192 + sb->s_firstdatazone-1;
	if (j >= sb->s_nzones)
		return 0;
	if (!(bh=getblk(dev,j)))    // 读取设备上的该新逻辑块数据（验证） 如果失败则死机
		panic("new_block: cannot get block");
	if (bh->b_count != 1)   // 将该新逻辑块清零 并置位更新标志和已修改标志 然后释放对应缓冲区 返回逻辑块号
		panic("new block: count is != 1");
	clear_block(bh->b_data);
	bh->b_uptodate = 1;
	bh->b_dirt = 1;
	brelse(bh);
	return j;
}
// 释放指定的i节点 复位对应i节点位图比特位
void free_inode(struct m_inode * inode)
{
	struct super_block * sb;
	struct buffer_head * bh;
    // 如果i节点指针=NULL 则退出
	if (!inode)
		return;
	if (!inode->i_dev) {    // 如果i节点上的设备号字段为0 说明该节点无用 则用0清空对应i节点所占内存区 并返回
		memset(inode,0,sizeof(*inode));
		return;
	}   // 如果此i节点还有其他程序引用 则不能释放说明内核有问题死机
	if (inode->i_count>1) {
		printk("trying to free inode with count=%d\n",inode->i_count);
		panic("free_inode");
	}   // 如果文件目录项连接数不为0 则表示还有其他文件目录项使用该节点 不应释放 而应该放回等
	if (inode->i_nlinks)
		panic("trying to free inode with links");
	if (!(sb = get_super(inode->i_dev)))    // 取i节点所在设备的超级块 测试设备是否存在
		panic("trying to free inode on nonexistent device");
	if (inode->i_num < 1 || inode->i_num > sb->s_ninodes)   // 如果i节点号=0 或大于该设备上i节点总数 则出错（0号i节点保留没有使用）
		panic("trying to free inode 0 or nonexistant inode");
	if (!(bh=sb->s_imap[inode->i_num>>13])) // 如果该i节点对应的节点位图不存在 则出错
		panic("nonexistent imap in superblock");
	if (clear_bit(inode->i_num&8191,bh->b_data))    // 复位i节点对应的节点位图中的比特位 如果该比特位已经等于0 则出错
		printk("free_inode: bit already cleared.\n\r");
	bh->b_dirt = 1; // 置 i 节点位图所在缓冲区已修改标志 并清空该i节点结构所占内存区
	memset(inode,0,sizeof(*inode));
}
// 为设备dev 建立一个新i节点 返回该新i节点的指针 在内存i节点表中获取一个空闲i节点表项 并从i节点位图中找一个空闲i节点
struct m_inode * new_inode(int dev)
{
	struct m_inode * inode;
	struct super_block * sb;
	struct buffer_head * bh;
	int i,j;
    // 从内存i节点表（inode-table）中获取一个空闲i节点项（inode）
	if (!(inode=get_empty_inode()))
		return NULL;
	if (!(sb = get_super(dev))) // 读取指定设备的超级块结构
		panic("new_inode with unknown device");
	j = 8192;   // 扫描i节点位图 寻找第一个0比特位 寻找空闲节点 获取放置该i节点的节点号
	for (i=0 ; i<8 ; i++)
		if (bh=sb->s_imap[i])
			if ((j=find_first_zero(bh->b_data))<8192)
				break;  // 若全部扫描完还没找到 或者位图缩招缓冲块无效（bh=NULL） 则返回0 退出（没有空闲i节点）
	if (!bh || j >= 8192 || j+i*8192 > sb->s_ninodes) {
		iput(inode);
		return NULL;
	}   // 置位对应新i节点的i节点位图相应比特位 如果已经置位 则出错
	if (set_bit(j,bh->b_data))
		panic("new_inode: bit already set");
	bh->b_dirt = 1;             // 置i节点位图所在缓冲区已修改标志
	inode->i_count=1;           // 初始化该i节点结构 引用计数
	inode->i_nlinks=1;          // 文件目录项链接数
	inode->i_dev=dev;           // i节点所在的设备号
	inode->i_uid=current->euid; // i节点所属用户id
	inode->i_gid=current->egid; // 组 id
	inode->i_dirt=1;            // 已修改标志置位
	inode->i_num = j + i*8192;  // 对应设备中的i节点号
	inode->i_mtime = inode->i_atime = inode->i_ctime = CURRENT_TIME;    // 设置时间
	return inode;               // 返回该i节点指针
}
